import java.util.Arrays;
import java.util.PriorityQueue;

public class HaffManTest {
    /**
     * 基于贪心算法的哈夫曼编码
     *
     */
    static class Node implements Comparable<Node>{
        char ch;
        int freq;
        Node left;
        Node right;

        public Node(char ch,int freq){
            this.ch=ch;
            this.freq=freq;
        }

        @Override
        public int compareTo(Node o){
            return this.freq-o.freq;
        }
    }

    public static Node buildHuffmanTree(char[] chars,int[] freqs){
        PriorityQueue<Node> queue = new PriorityQueue<>();
        for(int i=0;i< chars.length;i++){
            queue.offer(new Node(chars[i],freqs[i]));
        }

        while (queue.size()>1){
            Node left=queue.poll();
            Node right=queue.poll();
            Node parent=new Node('\0',left.freq+right.freq);

            parent.left=left;
            parent.right=right;
            queue.offer(parent);

        }
        return queue.poll();
    }

    public static void printHuffmanCode(Node root, String code) {
        if (root == null) {
            return;
        }
        if (root.ch != '\0') {
            System.out.println(root.ch + ": " + code);
        }
        printHuffmanCode(root.left, code + "0");
        printHuffmanCode(root.right, code + "1");
    }

    public static void main(String[] args) {
        char[] chars = {'a', 'b', 'c', 'd', 'e', 'f'};
        int[] freqs = {45, 13, 12, 16, 9, 5};
        Node root = buildHuffmanTree(chars, freqs);
        printHuffmanCode(root, "");
    }

}
